class Solution(object):
    def mincostTickets(self, days, costs):
        dp = [0 for _ in range(days[-1] + 1)]  # dp数组，每个元素代表到当前天数最少钱数，为下标方便对应，多加一个 0 位置
        days_idx = 0  # 设定一个days指标，标记应该处理 days 数组中哪一个元素
        # print(dp[0])
        for i in range(1, len(dp)):
            if i != days[days_idx]:  # 若当前天数不是待处理天数，则其花费费用和前一天相同
                dp[i] = dp[i - 1]
            else:
                # 若 i 走到了待处理天数，则从三种方式中选一个最小的
                #若从第一天开始至今还没够一天/七天/一个月，则当做在第一天买了日卡/周卡/月卡
                dp[i] = min(dp[max(0, i - 1)] + costs[0],  #昨天买了日卡
                            dp[max(0, i - 7)] + costs[1],  #七天前买了周卡
                            dp[max(0, i - 30)] + costs[2]) #一个月前买了月卡
                days_idx += 1
            # print(i,dp[i])
        return dp[-1]  # 返回最后一天对应的费用即可


days=[1,4,6,7,8,20]
costs=[2,7,15]
s=Solution()
print(s.mincostTickets(days,costs))